Livré à domicile ! (d'après BAC ES, Liban 2019) - Corrigé

Énoncé
Un restaurateur décide de proposer des livraisons à domicile. Il fait un essai avec huit clients. Sur le graphe ci-dessous, les sommets représentent les différents lieux d'habitation de ces huit clients. Les arêtes représentent les rues et les valeurs indiquent les durées moyennes des trajets exprimées en minutes.

1. Répondre aux questions suivantes en justifiant.
    a. Existe-t-il un parcours qui emprunte toutes les rues une et une seule fois ?
    b. Un tel parcours peut-il partir de  \(H_1\)  et y revenir ?

2. En utilisant l'algorithme de Dijkstra, déterminer le temps minimal pour aller de  \(H_4\)  vers  \(H_8\) . Préciser le trajet correspondant.

Solution

1. a. Afin de répondre à la question, on doit déterminer le degré de chacun des sommets de ce graphe.

\(\begin{array}{|c|c|} \hline \text{Sommet}&H_1&H_2&H_3&H_4&H_5&H_6&H_7&H_8 \\ \hline \text{Degré}&3&4&6&2&2&3&4&2 \\ \hline \end{array}\)

Ce graphe a exactement deux sommets de degré impair ; d'après le théorème d'Euler, il possède donc une chaîne eulérienne.
    b. Le graphe a deux sommets de degré impair, donc la chaîne eulérienne trouvée ne peut pas être un cycle. Si on part du sommet  \(H_1\) , il faut arriver au sommet  \(H_6\)

2. On peut déjà remarquer qu'il est possible de simplifier le problème en supprimant les étapes par  \(H_4\)  et  \(H_5\) , qui ne sont pas à une extrémité du parcours et sont de degré 2. On a donc une deuxième arête parallèle à  \(H_1-H_3\)  pondérée par un temps  \(t=8+15+7=30\)  largement supérieur à celui de l'arête existante.
On applique l'algorithme de Dijkstra au sous-graphe \(G'\)  comportant seulement les autres sommets.

\(\begin{array}{|c|c|} \hline \text{Sommet}&H_1&H_2&H_3&H_6&H_7&H_8 \\ \hline \text{Degré}&2&4&5&3&4&2 \\ \hline \end{array}\)

Algorithme de Dijkstra

De  \(H_1\)  on va en  \(H_2\) , qui est l'étape la plus rapide à atteindre avec un temps de 9 minutes, par rapport à \(H_3\)  qui est atteinte en 16 minutes.
Si on repart de  \(H_2\) , on va en  \(H_7\)  qui sera donc atteinte en un temps global de 17 minutes.
Comme  \(17>16\) , on vérifie si on aurait pu faire mieux en repartant de  \(H_3\) . Or, le trajet le plus rapide à partir de  \(H_3\)  amène en  \(H_7\)  avec un temps global de  \(16+4=20\)  minutes.
Il reste donc plus intéressant de faire  \(H_1 - H_2 - H_7\)  en  \(17\)  minutes. C'est le trajet que l'on conserve.
À partir de  \(H_7\)  on arrive directement en  \(H_8\)  en 9 minutes.
On a donc trouvé que le trajet le plus rapide est de  \(29\)  minutes, en faisant la chaîne : \(H_1 - H_2 - H_7 - H_8\) .